package gold.digger;

import gold.vo.TreeNode;

import java.util.*;

/**
 * Created by fanzhenyu02 on 2020/6/27.
 * common problem solver template.
 */
public class LC113 {
    public long startExecuteTime = System.currentTimeMillis();


    class Solution {
        public List<List<Integer>> pathSum(TreeNode root, int sum) {
            List<List<Integer>> res = new LinkedList<>();
            List<Integer> curRes = new ArrayList<>();
            if (root == null) return res;
            pathSumRecur(root, sum, res, curRes);
            return res;
        }

        public void pathSumRecur(TreeNode root, int sum, List<List<Integer>> res, List<Integer> curRes) {
            if (root == null) return;
            if ((root.left == null && root.right == null && root.val == sum)) {
                curRes.add(root.val);
                res.add(copyList(curRes));
                curRes.remove(curRes.size() - 1);
                return;
            }

            curRes.add(root.val);
            pathSumRecur(root.left, sum - root.val, res, curRes);
            pathSumRecur(root.right, sum - root.val, res, curRes);
            curRes.remove(curRes.size() - 1);
        }

        public List<Integer> copyList(List<Integer> oriList) {
            if (null == oriList) return null;
            List<Integer> copyList = new ArrayList<>();
            for (Integer integer : oriList) {
                copyList.add(integer);
            }

            return copyList;
        }
    }

    public void run() {
        Solution solution = new Solution();
        TreeNode root = TreeNode.createTree("[5,4,8,11,null,13,4,7,2,null,null,5,1]");
        System.out.println(solution.pathSum(root, 22));
    }

    public static void main(String[] args) throws Exception {
        LC113 an = new LC113();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
